1. Field of the Invention
A method that relates generally to telecommunications and, more particularly, to router algorithms and architectures for applying policy-based routing decisions to packets in a packet-based network, is disclosed.
2. Description of Related Art
As high-speed computer networks have become more widely available with increased bandwidth carrying capability, it has become possible to use computer networks for more diverse applications such as audio and video. Originally, the Internet was designed to carry digital data such as text and computer data files. With such digital files, Internet data transfers were satisfactory as long as the full file reached its destination in a reasonable time. Today, however, many new applications are placing real-time demands on the Internet. For example, when voice, music, video and still images are transferred, the timing of data arrival becomes crucial, or at least much more important, to the network's ability in carrying the information.
In times of network congestion, network routers' queues become full until they can no longer accommodate more traffic. Typically, routers have handled this situation by implementing a technique known as tail drop. Using tail drop, a router simply drops packets indiscriminately (that is, without regard to priority or class of service, etc.) until the output queue is no longer full. Dropping packets is the current feedback mechanism for TCP. When packets are dropped from a TCP connection, for example, from a source that is sending data faster than it can be handled by a router, the source may use a “slow start” technique to reduce its data transfer rate until congestion is reduced.
If a router uses tail drop as its congestion avoidance mechanism, the source will typically go into slow start mode whenever a burst of traffic causes the router's receive queue to fill. Then, the router will receive very little traffic from the source as the source tries to recover lost packets, after which the source may ramp up its data rate until the router begins to file again and the process is repeated. This mechanism causes data from a high-speed source to be sent in bursts with periods of low transmission rates between bursts. Congestion avoidance techniques that can handle bursts of traffic without dropping many (or all) packets during periods of congestion allow routers to maintain higher overall data transfer rates than those that use tail drop.
Lost information in the form of dropped packets can be unacceptable to businesses providing customers with Voice over IP (“VoIP”) or video over IP, who are often in competition with legacy suppliers of these services, such as local exchange carriers and cable television providers. The importance of satisfying the needs of bandwidth-hungry applications that are crucial to the business of providers has given rise to QoS (Quality of Service) mechanisms or controls. QoS simply means that there is some quantifiable measure of the service being provided. Several factors, for example, packet loss rate, a maximum delay rate, a guaranteed minimum bandwidth, or a maximum allowed bandwidth, etc., may be used to measure a network's QoS. Routers that use tail drop to handle congestion drop packets indiscriminately when network traffic is heavy, however, are not generally capable of providing differentiated QoS to network users.
Random Early Detection (“RED”), Flow Random Early Drop (“FRED”), and Weighted Random Early Detection (“WRED”) are among the methods that have been used to avoid congestion more effectively than tail dropping. All these methods are improvements over the technique of simply dropping packets when a gateway's queue is too full for its buffer to handle any further increase in packet flow. By implementing some variation of randomly dropping or marking packets before a gateway's buffers are overloaded, the methods can exercise some control over data flows to prevent congestion.
The RED technique controls congestion by dropping or marking packets with a drop probability (hence the term random) whenever the average queue size exceeds a predetermined minimum threshold. Because some packets are dropped before the queue is completely full, and because more packets are dropped as the average queue approaches a maximum threshold (i.e., the maximum queue size), RED and its variants can reduce the burst/low rate cycling problem associated with tail drop. RED gateways or routers keep the average queue size low while allowing occasional bursts of packets in the queue. During congestion, the probability that the router will notify a particular connection to reduce its data transfer rate (e.g., by marking or dropping packets) is roughly proportional to that connection's share of the bandwidth through the gateway. The RED router has no bias against bursty traffic and thus avoids “global synchronization” that is, many connections decreasing their congestion windows at the same time. RED is easy to implement and it won't unduly burden the gateway's processing resources.
RED, however, is not an optimal QoS control from the viewpoint of an end user of real-time sensitive, high-bandwidth data transmission; RED is best used where sources are able to reduce their throughput in response to dropped or marked packets, since packets will be dropped regardless of a source's response to a router's actions and also without regard to any priority differential of a connection, if traffic gets too heavy. Thus, a better solution is desired.
FRED improves on the performance of RED from the viewpoint of low flow-rate sources. FRED is more likely to drop or mark packets from sources with a higher number of packets queued. Further, FRED is not scalable for a large number of flows.
WRED, a variation of RED, is somewhat better at implementing QoS-sensitive congestion avoidance, since it selectively drops or marks packets based on either IP precedence or the resource reservation protocol (RSVP). Because the number of traffic flow types that can be classified by WRED is limited, however, a still better method of congestion avoidance is desired. In Internet Architecture, WRED is more suitable for core routers. A different kind of QOS algorithm that gives more control of traffic management for network administrators, is required for edge routers.